package interview;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description interview
 * @since JDK1.8
 *
 * 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
 */
public class NoRepeatStringArray {

    /**
     * 储存字符串的链表
     */
    private static final HashSet<String> LIST = new HashSet<>();

    public static String[] permutation(String s) {
        // 调用回溯递归
        backtrack(s.toCharArray(), 0);

        // 返回全排列数组
        return LIST.toArray(new String[0]);
    }

    private static void backtrack(char[] chs, int index) {
        // 假如已经移动到最后末尾，则添加此时的字符串
        if (index == chs.length) {
            LIST.add(String.valueOf(chs));
            return;
        }

        // 循环交换字符，形成全排列
        for (int i = index; i < chs.length; i++) {
            swap(chs, i, index);
            backtrack(chs, index + 1);
            // 回溯
            swap(chs, i, index);
        }
    }

    private static void swap(char[] chs, int i, int index) {
        char ch = chs[i];
        chs[i] = chs[index];
        chs[index] = ch;
    }

    public static void main(String[] args) {
        for (String s : permutation("qqe")) {
            System.out.println(s);
        }
    }
}
